// 204. 计数质数

//暴力超时
function five(n:number):number{
    if(n<2) return 0
    let ans = 0
    for(let i=2;i<n;i++){
        if(isPrime(i)) ans++
    }

    function isPrime(x:number):boolean{
        for(let i=2;i*i<=x;i++){
            if(x%i==0) return false
        }
        return true
    }


    return ans
}


//埃氏筛法
function countPrimes(n: number): number {
    if(n<2) return 0
    const isPrime = new Array<boolean>(n).fill(true)
    let ans = 0
    for(let i=2;i<n;i++){
        if(isPrime[i]){
            ans++
            for(let j=2;j*i<n;j++){
                isPrime[j*i]=false
            }
        }
    }
    return ans
};

console.log(countPrimes(10))